Ngày 1 tháng 4 năm 1933, tại Kẻ Sở, Đại diện Tông Tòa Hạt Đại diện Tông Tòa Hà Nội (quen gọi là Địa phận Hà Nội) Pierre Gendreau Đông phong chức linh mục cho thầy giảng Giuse Trịnh Như Khuê[8] và bổ nhiệm vị tân linh mục làm linh mục phó giáo xứ Khoan Vĩ.[11] Trong thời gian đảm trách vai trò này, linh mục Khuê tổ chức nhiều hoạt động tôn giáo nổi bật như lập đoàn Nghĩa binh của thiếu nhi, tổ chức các lễ trọng, rước kiệu Bà Maria, thăm viếng an ủi giáo dân, đặc biệt quan tâm đến những người khó khăn.[8] Sau một năm ở Khoan Vĩ, linh mục Khuê được thuyên chuyển về làm Giáo sư Tiểu chủng viện Hoàng Nguyên và ông đã dạy học tại chủng viện này trong vòng 7 năm.[6] Nhiều chủng sinh ấn tượng về trình độ và lòng yêu mến bà Maria của linh mục Trịnh Như Khuê.[8] Trong thời kỳ này, linh mục Khuê từng có ý định gia nhập dòng Phước Sơn, tuy vậy ý định không thành. Năm 1941, ông gia nhập dòng ba Phanxicô[12] và được Giám mục Đại diện Tông Tòa Hà Nội bổ nhiệm về nhận chức vụ linh mục phó giáo xứ Hàm Long, trợ giúp cho linh mục chính xứ là linh mục Dépaulis (Hương). Thời kỳ này, nạn đói nặng nề đã xảy ra ở miền Bắc Việt Nam vào năm 1945, linh mục Như Khuê đã cùng nhiều người tích cực tham gia các hoạt động cứu đói. Trong thời gian này, ông còn cử hành nghi thức Rửa tội cho 3.000 người.[8]

Năm 1947, linh mục Dépaulis về Pháp, linh mục Giuse Trịnh Như Khuê được chọn làm linh mục chính xứ giáo xứ Hàm Long, một giáo xứ lớn của Hà Nội. Với cương vị chính xứ, ông đã cho thành lập một tổ chức đoàn thể lấy tên "Đạo binh Đức Mẹ", còn gọi là "Đạo Binh Xanh".[6] Trong thời kỳ này, Trịnh Như Khuê đề cao tính kỷ luật trong binh đoàn ông đã thiết lập và luôn hỗ trợ những người muốn tìm hiểu giáo lý.[12] Ngày 12 tháng 8 năm 1948, linh mục Khuê công bố thành lập Legio Mariae Việt Nam, với chỉ 6 hội viên ban đầu.[13] Tháng 2 năm 1950, một linh mục người Việt mới được thụ phong đã được Giám mục địa phận thuyên chuyển về phụ giúp linh mục Khuê, đó là linh mục Giuse Maria Trịnh Văn Căn. Về sau này, cả hai vị linh mục chính và phó xứ đều trở thành những vị Hồng y của Giáo hội Công giáo Việt Nam.[6][11]